#define _CRT_SECURE_NO_WARNINGS 1
class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) {
        int n = nums.size();
        vector<int> f(n), g(n);
        f[0] = g[0] = 1;
        for (int i = 1; i < n; i++)
        {
            int maxlen = 0, maxi = -1;
            for (int j = 0; j < i; j++)
            {
                if (nums[i] == nums[j]) continue;
                else if (nums[i] < nums[j])
                {
                    if (f[j] > 0 && maxlen < f[j]) maxlen = f[j], maxi = j;
                }
                else
                {
                    if (g[j] > 0 && maxlen < g[j]) maxlen = g[j], maxi = j;
                }
            }
            if (maxi == -1) continue;
            if (nums[i] > nums[maxi]) f[i] = maxlen + 1;
            if (nums[i] < nums[maxi]) g[i] = maxlen + 1;
        }
        int maxl = 0;
        for (auto i : f) maxl = max(maxl, i), cout << i << ' ';
        cout << endl;
        for (auto i : g) maxl = max(maxl, i), cout << i << ' ';
        return maxl;
    }
};

class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) {
        int n = nums.size(), ret = 1;
        vector<int> f(n, 1), g(n, 1);
        for (int i = 1; i < n; i++)
        {
            for (int j = 0; j < i; j++)
            {
                if (nums[j] < nums[i]) f[i] = max(g[j] + 1, f[i]);
                else if (nums[j] > nums[i]) g[i] = max(f[j] + 1, g[i]);
            }
            ret = max(ret, max(f[i], g[i]));
        }
        return ret;
    }
};